package com.leetcode.weekly.contest.no283th;

import java.util.Arrays;

/**
 * @author 覃国强
 * @date 2022-03-06 10:39
 */
public class A02_向数组中追加K个整数 {

  public static void main(String[] args) {
    Solution solution = new Solution();
    int[] nums = {1000000000};
    int k = 1000000000;
    long sum = solution.minimalKSum(nums, k);
    System.out.println(sum);
  }

  static
  class Solution {
    public long minimalKSum(int[] nums, int k) {

      Arrays.sort(nums);

      long answer = 0;

      if (nums[0] > 1) {
        long count = Math.min(nums[0] - 1, k);
        answer += ((1 + count) * count) / 2;
        k -= count;
      }

      for (int i = 0; i < nums.length - 1 && k > 0; ++i) {
        if (nums[i + 1] - nums[i] > 1) {
          long count = Math.min(nums[i + 1] - nums[i] - 1, k);
          answer += nums[i] * count + ((1 + count) * count) / 2;
          k -= count;
        }
      }

      if (k > 0) {
        long count = k;
        answer += nums[nums.length - 1] * count + ((1 + count) * count) / 2;
      }

      return answer;
    }
  }

}
